package algorithm;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 基数排序
 */
public class RedixSort {
    //ASCII的取值汇范围
    public static final int ASCII_RANGE = 128;
    public static void main(String[] args) {
        String[] arr = {"qd","abc", "qwe","hhh","a","cws", "ope"};
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(radixSort(arr,3)));
    }

    /**
     *
     * @param array 数组
     * @param maxLength 单个词的最大长度
     * @return
     */
    public static String[]  radixSort(String[] array,int maxLength){
        //排序结果数据，用于存储每一次按位排序的临时结果
        String[] sortedArray = new String[array.length];
        //从低位，即个位开始比较，一直到高位
        for (int k=maxLength-1;k>=0;k--){
            //过程分成三步：
            //1.创建辅助排序数组，并把待排序的字符对号入座
            //这里为了代码简洁，直接使用ascii码范围作为数据长度
            int[] count = new int[ASCII_RANGE];
            for(int i=0;i<array.length;i++) {
                int index = getCharIndex(array[i], k);
                count[index]++;
            }
            System.out.println("first1 K:"+k+"|"+Arrays.toString(count));
            //2.统计数组做变形，后面的元素等于前面的元素之和 todo ???
            for ( int i =1;i<count.length;i++) {
               count[i] = count[i]+count[i-1];
            }
            System.out.println("first2 K:"+k+"|"+Arrays.toString(count));
            //3.倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
            for ( int i=array.length-1;i>=0;i--) {
                int index = getCharIndex(array[i], k);
                int sortedIndex = count[index]-1;
                System.out.println(array[i]+"|"+k+"|"+index+"|"+sortedIndex);
                sortedArray[sortedIndex] = array[i];
                count[index]--;
            }
            System.out.println("first3 k:"+k+"|"+Arrays.toString(sortedArray));
            //下一轮排序需要以上一轮的排序结果为基础，因此把结果复制给array
            array = sortedArray.clone();
        }
        return array;
    }
    //获取字符第K位所对应的ascii码序号
    public static int getCharIndex(String str, int k){
        //如果字符串长度小于K,直接返回0，相当于长度不足补位0
        if (str.length() < k+1) {
            return 0;
        }
        return str.charAt(k);
    }
}
